package algorithm.leetcode.I801to1000;

import java.util.LinkedList;
import java.util.List;

public class Q842 {

    public List<Integer> splitIntoFibonacci(String num) {
        LinkedList<Integer> curr = new LinkedList<>();
        List<List<Integer>> res = new LinkedList<>();

        dfs(res, curr, 0, num);

        return res.size() > 0 ? res.get(0) : new LinkedList<>();
    }

    private void dfs(List<List<Integer>> res,
                     LinkedList<Integer> curr,
                     int start,
                     String num) {
        // 回溯终了
        if (start == num.length() && curr.size() > 2) {
            res.add(new LinkedList<>(curr));
            return;
        }

        int size = curr.size();
        int canTryLen = num.length() - start;
        for (int i = 1; i <= canTryLen; i++) {
            String subStr = num.substring(start, start + i);
            // 当心解析溢出,先用判断长度,不大于10^11-1,并且用long接受,缓冲2^32~10^11-1这部分数字
            // 以0开头的子串只允许出现0
            if ((!subStr.startsWith("0") || subStr.equals("0")) && i <= 10) {
                long temp = Long.parseLong(subStr);
                // 砍掉2^32~10^11-1这部分数字
                // 如果curr的长度为0或1说明正在添加第1或第2个数字,不需要判断是否符合直接添加
                // 如果curr的长度为2,说明正在添加第3个数字,需要判断这个数字是否符合斐波那契
                if (temp <= Integer.MAX_VALUE && (size < 2 || curr.get(size-2) + curr.get(size-1) == temp)) {
                    curr.addLast((int) temp);
                    dfs(res, curr, start+i, num);
                    curr.removeLast();
                }
            }
        }
    }

    public static void main(String[] args) {
        Q842 q842 = new Q842();
        // System.out.println(Long.parseLong("47483647214748364221"));
        System.out.println(q842.splitIntoFibonacci("47483647214748364221"));
    }

}
